235. 二叉搜索树的最近公共祖先

Similar Question

leading to the advanced question

Solution Tips

方案一: Common Path

var lowestCommonAncestor = function(root, p, q) {
    // 找 path , path 里的公共部分就是共同的祖先, 找到最先的那个
    // find all path, if both found, break;
    // 然后还需要再按照 path
    const stack = [root];
    const pathStack = [[root]];
    let pPath = [];
    let qPath = [];

    while (stack.length) {
        const node = stack.pop();
        const curPath = pathStack.pop();

        if (node) {
            if (node.val === p.val) {
                pPath = curPath;
            }

            if (node.val === q.val) {
                qPath = curPath;
            }

            if (node.left) {
                stack.push(node.left);
                const newPath = [...curPath, node.left]
                pathStack.push(newPath);
            }
            if (node.right) {
                stack.push(node.right);
                const newPath = [...curPath, node.right]
                pathStack.push(newPath);
            }
        }
    }

    // 找出 pPath 和 curPath 的公共部分
    const commonPath = [];
    for (let i = 0; i < pPath.length; i++) {
        if (pPath[i]?.val === qPath[i]?.val) {
            commonPath.push(pPath[i]);
        }
        else {
            break;
        }
    }

    return commonPath[commonPath.length - 1]
};

方案二: 利用 BST 性质

如果 curVal 大于两者, 说明一定都在左子树, 所以公共祖先也一定在左子树

类似的, 如果小于, 则是一定都在右子树.

并且, 有且仅有一个节点可以做到, 一个大于, 一个小于, 这个节点就是两者的最近的公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_p = getPath(root, p);
        List<TreeNode> path_q = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p.get(i) == path_q.get(i)) {
                ancestor = path_p.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }
}